Conventionally, regarding a finite automaton for character string matching (pattern matching), there has been employed a method using a Non-deterministic Finite Automaton (NFA) that allows multiple transition destinations from one state for the same character, or a method using a Deterministic Finite Automaton (DFA) that does not allow multiple transition destinations.
For example, an NFA can be generated based on a syntax tree constructed from the search target condition, such as a given regular expression, as described in Patent Document 1 and Non-Patent Document 1, A DFA can be generated using an NFA.
In general, with the state of a NFA or a DFA saved in a memory, software-based pattern matching is performed by retrieving the state information from the memory each time a state transition occurs. In this case, when an input character is received, an NFA has multiple states as the destinations of transitions from one state and, so, it is impossible to determine to which state the NFA should move to produce a correct result. Therefore, the NFA moves to one of the states to perform processing and, if the processing fails, moves to another state using the backtrack method.
On the other hand, a DFA has only one transition destination from one state when an input character is received, meaning that a DFA has advantages in that the processing is performed faster than an NFA but has disadvantages in that the number of states is larger than that of an NFA and, so, a large amount of memory is required.
To solve such software-based pattern matching problems, an NFA-based high-speed pattern matching method is recently introduced in which an NFA is built directly into a hardware circuit to take full advantage of high-speed processing due to parallel operations (Non-Patent Document 2). Another method is that a higher search throughput is achieved by increasing the number of input characters that can be processed in one clock cycle (Non-Patent Document 3). A still another method is also proposed in which the search throughput is increased by performing NFA state transition condition with multiple characters so that a character string of multiple characters are received simultaneously (Non-Patent Document 4, Non-Patent Document 5).    Patent Document 1:    Japanese Patent Kokai Publication No. JP-P2003-242179A (paragraphs 20-34, FIG. 1-FIG. 9)    Non-Patent Document 1:    Standard text: Algorithm and Data Structure for C Programmers (pp. 297-330, Yoshiyuki Kondo, 1998)    Non-Patent Document 2:    Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (pp. 227-238, Reetinder Sidhu, Viktor K. Prasanna, 2001)    Non-Patent Document 3:    Proceedings of 2004 IEEE International Conference on Field-Programmable Technology (pp. 25-32, Peter Sutton, 2004)    Non-Patent Document 4:    Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (pp. 249-257, Christopher R. Clark, David F. Schimmel, 2004)    Non-Patent Document 5:    Journal of the Information Processing Society of Japan:    Computing system Vol. 46, No. SIG12 (ASCII) (pp. 120-128, Toshihiro Katashita, Atsushi Maeda, Masato Ono, Kenji Toda, and Yoshinori Yamaguchi, 2005)